一日总有七八千的杂念
每一秒都很可耻
下一秒亦然
第一章：什么是组合数学
碎碎念：
组合数学关心的问题就是把某个集合中的对象排列成某种模式，使其满足一些指定的规则。
以下是两种反复出现的通用问题:
- 对于8 $\times$ 8的标准棋盘，通常把方格交替着染上黑色和白色。
31BW$ \neq$32 B+30W
color diagram into two colors as a chessboard - m $\times$ n 的标准棋盘完美覆盖b格牌(连续b个1$\times1的方格并排连接而成$)的条件是：
当且仅当b是m或者n的一个因子。 - 轮廓线dp：
用2格牌覆盖n$\times$m的棋盘，有多少种方案。
UVA11270经典轮廓线dp,可配合刘汝佳蓝书 - 断层线：
4$\times$4的棋盘的多米诺骨牌的完美覆盖不可能不产生断层线。
幻方
1.定义:
一个n阶幻方就是由整数$1, 2, 3, ……,n^2$按照某种方式构成的$n\times n$的矩阵:他的每一行每一列以及对角线上的数字总和总是相等。都等于某个整数S。S称为这个幻方的幻和。
以上是幻和为15的三阶幻方和幻和为34的四阶幻方。
2.幻和:
由定义，我们可以得到关系式$nS=\frac{n^2(n^2+1)}{2}\rightarrow S =\frac{n(n^2+1)}{2}$
3.构造幻方的一般方法：
①不存在2阶幻方。
②对于其他n阶的幻方，我们总能构造出n阶幻方。构造方法
4.对于幻方体（三维）：
$S = \frac{n^4+n}{2}$
不存在2阶幻方体，3阶幻方体。
四色问题
四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色”。
用数学语言表示即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1234这四个数字之一来标记而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。
36军官问题
欧拉曾提出一个问题：即从不同的6个军团各选6种不同军阶的6名军官共36人，排成一个6行6列的方队，使得各行各列的6名军官恰好来自不同的军团而且军阶各不相同，应如何排这个方队？如果用(1，1)表示来自第一个军团具有第一种军阶的军官，用(1，2)表示来自第一个军团具有第二种军阶的军官，用(6，6)表示来自第六个军团具有第六种军阶的军官，则欧拉的问题就是如何将这36个数对排成方阵，使得每行每列的数无论从第一个数看还是从第二个数看，都恰好是由1、2、3、4、5、6组成。历史上称这个问题为三十六军官问题。
以下以九名军官分别来自3个不同的军衔和三个不同的军团为例。
$
\begin{bmatrix}
1 & 2 & 3 \
3 & 1 & 2 \
2 & 3 & 1 \
\end{bmatrix}
$ $
\begin{bmatrix}
1 & 2 & 3 \
2 & 3 & 1 \
3 & 1 & 2 \
\end{bmatrix}
$ $\rightarrow$$
\begin{bmatrix}
(1,1) & (2,2) & (3,3) \
(3,2) & (1,3) & (2,1) \
(2,3) & (3,1) & (1,2) \
\end{bmatrix}
$
军衔矩阵 军团矩阵 并置矩阵
1.不存在二阶正交拉丁方。不存在六阶正交拉丁方。
2.欧拉猜想4k+2不存在（k=2，3，…，n）正交拉丁方是错误的。对于$n\gt6 $ 存在正交拉丁方。
3.数独是特殊的九阶拉丁方。
最短路径问题
From ZJU JingBang Chen 2020Wannafly Winter Camp Div1 Graph Theory ppt
由于参加的是Div2所以未能听到他的讲课内容，先挂上图，以后有时间要研究的。
相互重叠的圆
考虑平面上以普通位置相互重叠的$n$个圆，他们相互重叠(这里指的是每一对圆之间交于两个不同的点，也就是不允许相交和相切的圆)这$n$个圆在平面内构成的数量是$h(n)$ ，以下求$h(n)$的值。
解决这一类计数问题的一个方法就是尝试着确定当从$n-1$个圆$\gamma1,\gamma_2,…,\gamma{n-1}$变到n个圆$\gamma1,\gamma_2,…,\gamma{n}$时出现的区域变化。用更一般的语言表述如下：我们尝试着确定$h(n)$的一个递推关系，即用前面的值表示$h(n)$。
我们假设$n \ge 2$而且在平面上已经画出普通位置下相互重叠的圆$\gamma1,\gamma_2,…,\gamma{n-1}$，它们构建了$h{n-1}$个区域。然后加入第$n$个圆$\gamma_n$使得在普通位置下有n个相互重叠的圆。前$n-1$个圆中的每一个圆都与第n个圆相交出两个点，因为这些圆都处于普通位置上，所以我们得到$2(n-1)$个不同点$P_1，P_2,…，P{2(n-1)}$。这$2(n-1)$个点把圆$\gamman$分割成$2(n-1)$条弧：$P_1和P_2$之间的弧，$P_2$和$P_3$之间的弧,…，$P{2(n-1)-1}和P{2(n-1)}$之间的弧，以及$P{2(n-1)}与P1$之间的弧。这2(n-1)条弧中的每一条弧都把由前面$n-1$个圆$\gamma_1,\gamma_2,…,\gamma{n-1}$构成的区域分成两个区域，创建出额外$2(n-1)$个区域。因此，$h(n)$满足下面的关系：
$h(n) = h(n-1) + 2(n-1)\quad\quad (n\ge2)$
利用递推关系和$\sum i$的求和公式可以得到 $h(n) = n^2-n+2 \quad (n\ge2)$
Nim游戏
if SG = 0 先手必败
else 先手必胜
Attention：是公平组合游戏，有些游戏是不公平的。
第二章 排列与组合
四个基本的计数定理
- 加法原理：
运用加法原理的技巧是把集合S划分成少量容易处理的部分。 - 乘法原理：
乘法原理是加法原理的一个推论。
eg.正因素个数的确定：
减法原理：
除法原理：
集合的排列
集合的组合（子集）
多重集合的排列
多重集合的组合
有限概率
第三章 鸽巢原理
鸽巢原理：简单形式
鸽巢原理：加强版
Ramsey定理
- Ramsey定理的最流行且容易理解的例子是:
在6个（甚至更多的）人中，或者有三个人，他们每两个人都相互认识，或者有三个人，他们每两个人都相互不认识。 - 定理内容：
如果$m \ge 2 \quad\&\&\quad n \ge 2$是两个整数，则存在正整数p，使得语言描述：Ramsey定理说的是给定 m 和 n，存在正整数p，使得当把$K_p$的边着成红色或者蓝色时，或者存在一个红色$K_m$，或者存在一个蓝色$K_n$。无论$K_p$如何染色，都保证红色$K_m$或者蓝色$K_n$的存在性。如果$K_p\rightarrow K_m,K_n$，那么对于任何满足$q\ge p$的整数q，$K_q\rightarrow K_m,K_n$都成立。用$r(m,n)$表示使得$K_p\rightarrow K_m,K_n$，成立的最小整数p。
证明略。 - Ramsey(拉姆塞)定理只给出了Ramsey数的存在性问题，并没有给出求解Ramsey数的有效方法。确定Ramsey数是一个NP难题。
- $r(m,n) = r(n,m) \quad r(2,n) = n$
- 以下是目前已知的二色经典的非平凡的Ramsey数$r(m,n)$
ps:表中两个取等$40\le r(3,10) \le 43$表示$K{43} \rightarrow K_3,K{10} $ 而 $K{39} \nrightarrow K_3,K{10} $ - Ramsey定理可以扩展到任意多种颜色的情况，已知$r(3,3,3) = 17$。
- Ramsey还有更一般的形式。。。此处等待填坑。
$r_1(q_1,q_2 ……q_k) = q_1+q_2+……+q_k-k+1$ 此处说明Ramsey是鸽巢原理的加强版的扩展。
求一般的$r_t(q_1,q_2 ……q_k) $就很难求，目前已知很少。第四章：生成组合和排列
我们的宇宙，在某种意义上是上帝所创造的最好的一个。
——戈特弗里德·威廉·莱布尼茨